package agorithm.week1.classTwo;

/**
 * 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 *
 * Range Sum Query 2D
 * 上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
 *
 *
 *
 * 示例：
 *
 * 给定 matrix = [
 *   [3, 0, 1, 4, 2],
 *   [5, 6, 3, 2, 1],
 *   [1, 2, 0, 1, 5],
 *   [4, 1, 0, 1, 7],
 *   [1, 0, 3, 0, 5]
 * ]
 *
 * sumRegion(2, 1, 4, 3) -> 8
 * sumRegion(1, 1, 2, 2) -> 11
 * sumRegion(1, 2, 2, 4) -> 12
 *
 *
 * 提示：
 *
 * 你可以假设矩阵不可变。
 * 会多次调用 sumRegion 方法。
 * 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
 */
public class NumMatrix {

    private int[][] sum ;
    public NumMatrix(int[][] matrix) {
        if (matrix.length >0) {
            sum = new int[matrix.length+1][matrix[0].length+1];
            // 第一步求二维数组前缀和的二维数组
            // 公式：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j]
            for ( int i = 1 ;i < sum.length ;i++){
                for ( int j = 1 ;j < sum[i].length ;j++){
                    sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
                }
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(sum!=null && sum.length>0){
            return sum[row2+1][col2+1] -sum[row1][col2+1]-sum[row2+1][col1] + sum[row1][col1];
        }else{
            return 0;
        }
        // 第二步子区间和公式： sum[i][j] - sum[p][q] => sum = sum[i][j] -sum[i-p][j]-sum[i][j-q] + sum[i-p][j-q];
        // 注意这个时候的sum如下，所以每个行列都要+1；
        // 0;0;0;0;0;0
        // 0;3;3;4;8;10
        // 0;8;14;18;24;27
        // 0;9;17;21;28;36
        // 0;13;22;26;34;49
        // 0;14;23;30;38;58
        // return  sum[row2+1][col2+1] -sum[row1][col2+1]-sum[row2+1][col1] + sum[row1][col1];

    }
}
